Turbo codes are a kind of error correction codes, and have been prevalently applied to a variety of wireless communication systems due to their exceptional error correction ability.
In a transmitter, for example, referring to FIG. 1, a conventional turbo encoder is used to encode information bits as an input code, and generally includes two convolutional encoders 11, 12, an interleaver 13 and a puncture module 14. The input code is encoded in normal and interleaved order phases. Along with the input code, i.e., systematic bits, first parity check bits as a first parity check code and second parity check bits as a second parity check code are produced respectively in the normal and interleaved order phases. Before transmitting the input code and the first and second parity check codes through a wireless communication channel, the puncture module 14 conducts puncturing operations for the input code and the first and second parity check codes by deleting some code bits from the input code and the parity check codes to raise the transmission code rate. Puncturing operations are categorized into periodical and non-periodical types. The periodical puncturing implies that bit positions and the number of punctured bits are the same in every period of the code.
Referring to FIG. 2, an example of encoding and puncturing operations for a 15-bit data code, denoted as S00S01S02S03S04S05S06S07S08S09S10S11S12S13S14, is shown. In the beginning, a rate-1/2 encoder (not shown) of a transmitter encodes the 15-bit data code to produce an output that includes a 15-bit parity check code denoted as P00P01P02P03P04P05P06P07P08P09P10P11P12P13P14 and the 15-bit data code. Then, in a puncturing operation, 12 parity bits are deleted from the 15-bit parity check code (but no data bit is deleted from the data code in this example) to thereby produce a punctured 15-bit parity check code denoted as P00**P03********P12**, where “*” denotes a punctured bit.
In a receiver, for example, referring to FIG. 3, a conventional turbo decoder system is used to decode received turbo codes, e.g., the data code and the first and second parity check codes (i.e., systematic bits, first parity check bits and second parity check bits) punctured by and transmitted from the transmitter, between the normal and interleaved order phases iteratively. The conventional turbo decoder system includes a depuncture module 21, and an iterative decoder 20 that consists of two soft-in/soft-out (SISO) decoders 22, 23, two interleavers 25, 26 and a deinterleaver 24. Before iterative decoding, in order to reconstruct original codes, for example, the non-punctured data code and the non-punctured parity check codes, the depuncture module 21 conducts depuncturing operations by inserting zeros into each received code respectively at all punctured bit positions, thereby extending the length of the received code to its non-punctured length. In other words, each depunctured code can be deemed as the original non-punctured code by the turbo decoder.
Referring again to FIG. 2, as the same example, in the de-puncturing operation of a receiver, 12 zeros denoted as “0” are inserted into the received parity check code respectively at all the punctured bit positions to thereby produce a depunctured 15-bit parity check code denoted as P0000P0300000000P1200.
In each decoding phase of a SISO decoder, a SISO algorithm proposed in a first article by Hagenauer, E. Offer, and L. Papke, “Iterative decoding of binary block and convolutional codes,” IEEE Trans. Inf. Theory, vol. 42, no. 2, pp. 429-445, March 1996, is performed, and an extrinsic value for each data symbol is produced. These extrinsic values are delivered into a next decoding phase as the a priori input(s) for each dedicated data symbol. By updating and exchanging soft values in each decoding phase, reliable log likelihood ratio (LLR) of a posteriori value(s) for each data symbol can be obtained to achieve better bit error rate (BER).
A decoding trellis is essential to the SISO decoders for performing the SISO algorithm and delivering the soft values. Adopted to execute maximum a posteriori probability (MAP) proposed in a second article by L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE. Trans. Inf. Theory, vol. IT-20, pp. 284-287, March 1974 are two types of decoding trellises. One is a conventional trellis, and the other is a reciprocal dual trellis proposed in S. Riedel, “Symbol-by-symbol MAP decoding algorithm for high-rate convolutional codes that use reciprocal dual codes,” IEEE J. Sel. Areas Commun., vol. 16, no. 2, pp. 175-185, February 1998. To save hardware resources and output latency, a sliding window (SW) decoding schedule disclosed in a third article by S. A. Barbulescu, “Sliding window and interleaver design,” IET Electronics letters, vol. 37, no. 21, pp. 1299-1300, October 2001, is generally applied in the turbo decoder.
The SISO decoders with the conventional trellis can achieve good hardware efficiency for low code rate operations, for example, 1 Gbps throughput at 966 mW power consumption disclosed in a fourth article by C. Roth, S. Belfanti, C. Benkeser, and Q. Huang, “Efficiency parallel turbo decoding for high throughput wireless systems,” IEEE Trans. Circuits Syst. I, vol. 58, no. 6, pp. 1412-1420, June 2014. While the conventional trellis is applied to carry out MAP algorithm, the size of SW has to be enlarged to maintain good error correction ability as the operation code rate rises. It is noted that, in high code rate operations, the SISO decoders with the conventional trellis may suffer from relatively long decoding latency and relatively large circuit area because a wide size of SW is required.
In order to solve the aforementioned issues, the SISO decoders with the reciprocal dual trellis, as disclosed in a fifth article by C.-Y. Lin, C.-C. Wong, and H.-C. Chang, “A 40 nm 535 Mbps multiple code-rate turbo decoder chip using reciprocal dual trellis,” IEEE J. Solid-state Circuits, vol. 48, no. 11, pp. 2662-2670, November 2013, have been proven to have better hardware efficiency, i.e., higher throughput per area (Mbps/k-gates), for high rate code operations. The SW decoding schedule can be applied to the SISO decoders with the reciprocal dual trellis for producing LLR. Therefore, for the iterative decoder 20 of FIG. 3, some computation units in the SISO decoders 22, 23 can be shared when integrating the reciprocal dual trellis and the conventional trellis. While decoding periodically punctured codes, parallel LLR computation units in the reciprocal dual trellis have to be activated simultaneously to boost decoding speed. However, the SISO decoders with the reciprocal dual trellis are limited to applications of periodically punctured codes.
Therefore, turbo decoders with a single one of the aforementioned decoding trellises may not conform to high-throughput requirements for arbitrary code rate operations.